package leetcode;

import java.util.Arrays;

/**
 * 贪心算法：合并区间
 */
public class Solution36 {
    class Solution {
        public int[][] merge(int[][] intervals) {
            LinkedList<int[]> result = new LinkedList<>();
            Arrays.sort(intervals,(a, b) -> Integer.compare(a[0],b[0]));
            result.add(intervals[0]);

            for(int i = 1; i < intervals.length;i++){
                if(intervals[i][0] <= result.getLast()[1]){
                    int start = result.getLast()[0]; //左区间
                    int end = Math.max(intervals[i][1],result.getLast()[1]); //右区间
                    result.removeLast();
                    result.add(new int[]{start, end});
                }else{
                    result.add(intervals[i]);
                }
            }
            return result.toArray(new int[result.size()][]);
        }
    }
}
